994C - Two Squares - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define stup ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define EPS 1e-10
#define PI 3.14159265359
const ll mod = 1e9 + 7;
const ll INF = 3e18;
const int N = 2e5 + 1;
//#define endl '\n'

int sgn(int x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0) : x(x), y(y) {}
    bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
    bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
    P operator+(P p) const { return P(x+p.x, y+p.y); }
    P operator-(P p) const { return P(x-p.x, y-p.y); }
    P operator*(T d) const { return P(x*d, y*d); }
    P operator/(T d) const { return P(x/d, y/d); }
    T dot(P p) const { return x*p.x + y*p.y; }
    T cross(P p) const { return x*p.y - y*p.x; }
    T cross(P a, P b) const { return (a-*this).cross(b-*this); }
    T dist2() const { return x*x + y*y; }
    double dist() const { return sqrt((double)dist2()); }
    // angle to x-axis in interval [-pi, pi]
    double angle() const { return atan2(y, x); }
    P unit() const { return *this/dist(); } // makes dist()=1
    P perp() const { return P(-y, x); } // rotates +90 degrees
    P normal() const { return perp().unit(); }
    // returns point rotated 'a' radians ccw around the origin
    P rotate(double a) const {
        return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
    friend ostream& operator<<(ostream& os, P p) {
        return os << "(" << p.x << "," << p.y << ")"; }
};
#define point Point<int>
bool onSegment(point s, point e, point p) {
    return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

vector<point> segInter(point a, point b, point c, point d) {
    auto oa = c.cross(d, a), ob = c.cross(d, b),
            oc = a.cross(b, c), od = a.cross(b, d);
    // Checks if intersection is single non-endpoint point.
    if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0)
        return {(a * ob - b * oa) / (ob - oa)};
    set<point> s;
    if (onSegment(c, d, a)) s.insert(a);
    if (onSegment(c, d, b)) s.insert(b);
    if (onSegment(a, b, c)) s.insert(c);
    if (onSegment(a, b, d)) s.insert(d);

    vector<point>res;
    for (auto x : s){
        res.push_back(x);
    }
    return res;
}
bool inPolygon(vector<point> &p, point a, bool strict = true) {
    int cnt = 0;
    for (int i = 0; i<p.size();i++) {
        point q = p[(i + 1) % p.size()];
        if (onSegment(p[i], q, a)) return !strict;
        //or: if (segDist(p[i], q, a) <= eps) return !strict;
        cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0;
    }
    return cnt;
}
void solve ()
{
    vector<point> s1;
    vector<point> s2;
    for (int i = 1; i<=4;i++){
        int x,y; cin >> x>>y;
        s1.push_back(point(x,y));
    }
    for (int i = 1; i<=4;i++){
        int x,y;
        cin >> x >> y;
        s2.push_back(point(x,y));
    }

    for (int i = 0; i<4;i++){
        point p = s1[i];
        point q = s1[(i+1)%4];
        for (int j = 0; j<4;j++){
            point p2 = s2[j];
            point q2 = s2[(j+1)%4];
            if (segInter(p,q,p2,q2).size()){
                cout << "YES" << endl;
                return;
            }
        }
    }

    for (int i = 0; i<4;i++){
        if (inPolygon(s2,s1[i]) || inPolygon(s1,s2[i])){
            cout << "YES" << endl;
            return;
        }
    }

    cout << "NO" << endl;
}


int32_t main() {
    stup;
    int tes = 1;
    //cin >> tes;
    for (int i = 1; i<=tes;i++)
    {
        solve();
    }
}